import javafx.util.Pair;

import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedList;

/**
* @description: TODO
* @author hewei
* @date 2022/9/21 14:49
* @version 1.0
*/

public class ShortestBridge {

    public static void main(String[] args) {
        int[][] nums = {{1,1,1,1,1},{1,0,0,0,1},{1,0,1,0,1},{1,0,0,0,1},{1,1,1,1,1}};
        System.out.println(new ShortestBridge().shortestBridge(nums));
    }

    int[][] step = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    public int shortestBridge(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        Deque<Pair<Integer, Integer>> queue = new LinkedList<>();
        HashSet<Pair<Integer, Integer>> set = new HashSet<>();
        boolean flag = true;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    if (flag) {
                        grid[i][j] = 2;
                        dfs(grid, i, j);
                        flag = false;
                    } else {
                        Pair<Integer, Integer> pair = new Pair<>(i, j);
                        queue.add(pair);
                        set.add(pair);
                    }
                }
            }
        }
        int count = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                Pair<Integer, Integer> poll = queue.poll();
                for (int[] ints : step) {
                    int x = poll.getKey() + ints[0];
                    int y = poll.getValue() + ints[1];
                    Pair<Integer, Integer> pair = new Pair<>(x, y);
                    if (!set.contains(pair) && x >= 0 && x < m && y >= 0 && y < n) {
                        if (grid[x][y] == 2) return count;
                        set.add(pair);
                        queue.add(pair);
                    }
                }
            }
            ++count;
        }
        return count;
    }

    public void dfs(int[][] grid, int i, int j) {
        int m = grid.length;
        int n = grid[0].length;
        for (int[] ints : step) {
            int x = ints[0] + i;
            int y = ints[1] + j;
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                grid[x][y] = 2;
                dfs(grid, x, y);
            }
        }
    }
}
